import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class lengthOfLIS {
    /**
     * 最长递增子序列
     * 思路就是动态dp
     */
//    public static int method(int[] nums){
//        if(nums.length==0) return 0;
//        int[] dp = new int[nums.length]; //dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度。
//        int res = 0;
//        Arrays.fill(dp,1);
//        for(int i=0;i< nums.length;i++){
//            for(int j=0;j<i;j++){
//                if(nums[j]<nums[i]){
//                    dp[i] = Math.max(dp[i], dp[j]+1);
//                }
//            }
//            res = Math.max(res, dp[i]);
//        }
//        return res;
//    }
//
//    public static void main(String[] args) {
//        int[] nums={10, 9, 4, 5, 6, 3, 2};
//        int answer1 = method(nums);
//        System.out.println("最长的递增子序列长度为： " + answer1);
//    }

    /**
     * 此时修改下条件
     * 需要找到最长递增子序列的具体元素，而不是单纯返回长度了~
     * 思路：
     */
    public static List<Integer> findLIS(int[] nums){
        if(nums.length == 0) return new ArrayList<>();
        int[] dp=new int[nums.length];
        int[] prevIndex = new int[nums.length]; //用于记录每个位置的前一个索引
        Arrays.fill(dp, 1);
        Arrays.fill(prevIndex, -1);

        int maxLength = 0;
        int endIndex = 0;
        for(int i=0;i< nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i] && dp[j]+1>dp[i]){
                    dp[i] = dp[j] + 1;
                    prevIndex[i] = j;
                }
            }
            if(dp[i] > maxLength){
                maxLength = dp[i];
                endIndex = i;
            }
        }

        List<Integer> result = new ArrayList<>();
        int currentIndex = endIndex;
        while(currentIndex!=-1){
            result.add(nums[currentIndex]);
            currentIndex=prevIndex[currentIndex];
        }

        // 由于是从后向前添加的，需要反转
        List<Integer> finalRes=new ArrayList<>();
        for(int i=result.size() - 1; i>=0; i--){
            finalRes.add(result.get(i));
        }

        return finalRes;
    }

    public static void main(String[] args) {
        lengthOfLIS l=new lengthOfLIS();
        int[] nums={10, 9, 3, 4, 5, 6, 8, 7, 9, 11};
        List<Integer> list=l.findLIS(nums);
        System.out.println("最长递增子序列：" + list);
    }
}
